Search Results

Documents authored by Nenadov, Rajko


Document
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability

Authors: Rajko Nenadov, Angelika Steger, and Pascal Su

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.

Cite as

Rajko Nenadov, Angelika Steger, and Pascal Su. An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{nenadov_et_al:LIPIcs.ITCS.2021.60,
  author =	{Nenadov, Rajko and Steger, Angelika and Su, Pascal},
  title =	{{An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.60},
  URN =		{urn:nbn:de:0030-drops-135997},
  doi =		{10.4230/LIPIcs.ITCS.2021.60},
  annote =	{Keywords: Random Graphs, Hamilton Cycle, Perfect Matching, Linear Time, Sublinear Algorithm, Random Walk, Coupon Collector}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail